import java.util.ArrayList;
import java.util.List;

/**
 * Created by L.jp
 * Description:给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定s 是否可以由空格拆分为一个或多个在字典中出现的单词。
 *
 *输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。


 * User: 86189
 * Date: 2021-11-08
 * Time: 22:31
 */
//动态规划分析：
//    1.定义状态数组，每个下标存储的是能不能被拆分的布尔值,dp[i]表示这个i串能否被拆分为字典里面的序列
//    2.状态定义抽象为：求整个字符串能否被拆分为字典里面的单词序列就转换为每个子串能否被拆分
//    3.状态初始化：我们不知道第一个字符是否可以把字串拆分，所以我们需要借助0下标也就是空串来辅助递推到后面的子串，只有0下标串为true，才能按照状态转移方程推出后面的状态
//    4.状态转移方程：i<j && dp[j]为真 && (j+1,i)序列存在字典里
//    5.状态返回结果是：求得dp[s.length()]的结果为真就代表整个字符串可以被拆分为字典里面的单词序列
public class WordSplitting {
    public static boolean wordBreak(String s, List<String> wordDict){
        boolean[] canbebreak=new boolean[s.length()+1];//由于添加了空串的真值存储，所以要加1，dp[s.length]就是最后要求的结果
        //状态初始化：
        canbebreak[0]=true;//表示第一个串可以被空串和这个串拆分而成
        for(int i=1;i<=s.length();i++){//这里的i可以理解为前i个字符，求前一个字符时必须要知道第0个字符的真值，也就是我们假设的0下标为true
            for(int j=0;j<i;j++){
                if(canbebreak[j] && wordDict.contains(s.substring(j,i))){//当判断第一个字符时，需要加上空串的判断和判断第一个字符是否在字典里，所以这里是(j,i]
                    canbebreak[i]=true;
                    break;
                }
            }
        }
        return canbebreak[s.length()];//返回最后一个的真值，即表示前(s.length)个字符串可以拆分为字典里面的序列
    }
    public static void main(String[] args) {
        String s="leetcode";
        String s1="leet";
        String s2="code";
        List<String> list=new ArrayList<>();
        list.add(s1);
        list.add(s2);
        System.out.println(list);
        System.out.println("=========");
        System.out.println(wordBreak(s, list));
    }
}
